import heapq
import math

board = [[math.inf for _ in range(2022)] for _ in range(2022)]
for i in range(1, 2022):
    for j in range(i + 1, min(i + 22, 2022)):
        board[i][j] = i // math.gcd(i, j) * j
        board[j][i] = i // math.gcd(i, j) * j
for i in range(2022):
    board[i][i] = 0

distance = [math.inf for _ in range(2022)]
visited = [False] * 2022
heap = [(0, 1)]  # 距离和节点
while heap:
    distance_curr, curr = heapq.heappop(heap)
    visited[curr] = True
    if distance_curr == math.inf: continue
    # print(curr)
    if curr == 2021:
        print(distance_curr)
    for next_node in range(max(0, curr - 21), min(curr + 22, 2022)):
        if visited[next_node]: continue
        new_dist = distance_curr + board[curr][next_node]
        if new_dist < distance[next_node]:
            distance[next_node] = new_dist
            heapq.heappush(heap, (new_dist, next_node))
